package com.gonglin.test.sort;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.List;
import java.util.Map;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.TreeMap;
import java.util.HashMap;
import java.util.Queue;

/*
DISTRIBUTION OF DICTIONARY:
Read the words...88984
1       1
2       48
3       601
4       2409
5       4882
6       8205
7       11989
8       13672
9       13014
10      11297
11      8617
12      6003
13      3814
14      2173
15      1169
16      600
17      302
18      107
19      53
20      28
Elapsed time FAST: 2.8 vs 3.8
Elapsed time MEDIUM: 50.9 vs 50.5
Elapsed time SLOW: 95.9 vs 96.1 (H vs T)
**/

public class WordLadder
{
    public static List<String> readWords( BufferedReader in ) throws IOException
    {
        String oneLine;
        List<String> lst = new ArrayList<String>( );
        
        while( ( oneLine = in.readLine( ) ) != null )
            lst.add( oneLine );
        
        return lst;
    }    
    
    // Returns true is word1 and word2 are the same length
    // and differ in only one character.
    private static boolean oneCharOff( String word1, String word2 )
    {
        if( word1.length( ) != word2.length( ) )
            return false;
        
        int diffs = 0;
        
        for( int i = 0; i < word1.length( ); i++ )
            if( word1.charAt( i ) != word2.charAt( i ) )
                if( ++diffs > 1 )
                    return false;
                    
        return diffs == 1;
    }
    
    private static <KeyType> void update( Map<KeyType,List<String>> m, KeyType key, String value )
    {
        List<String> lst = m.get( key );
        if( lst == null )
        {
            lst = new ArrayList<String>( );
            m.put( key, lst );
        }
        
        lst.add( value );
    }
    
    // Computes a map in which the keys are words and values are Lists of words
    // that differ in only one character from the corresponding key.
    // Uses a quadratic algorithm (with appropriate Map).
    public static Map<String,List<String>> computeAdjacentWordsSlow( List<String> theWords )
    {
        Map<String,List<String>> adjWords = new HashMap<String,List<String>>( );
        
        String [ ] words = new String[ theWords.size( ) ];
        
        theWords.toArray( words );    
        for( int i = 0; i < words.length; i++ )
            for( int j = i + 1; j < words.length; j++ )
                if( oneCharOff( words[ i ], words[ j ] ) )
                {
                    update( adjWords, words[ i ], words[ j ] );
                    update( adjWords, words[ j ], words[ i ] );
                }
        
        return adjWords;
    }
    
    // Computes a map in which the keys are words and values are Lists of words
    // that differ in only one character from the corresponding key.
    // Uses a quadratic algorithm (with appropriate Map), but speeds things up a little by
    // maintaining an additional map that groups words by their length.
    public static Map<String,List<String>> computeAdjacentWordsMedium( List<String> theWords )
    {
        Map<String,List<String>> adjWords = new HashMap<String,List<String>>( );
        Map<Integer,List<String>> wordsByLength = new HashMap<Integer,List<String>>( );
        
          // Group the words by their length
        for( String w : theWords )
            update( wordsByLength, w.length( ), w );
        
          // Work on each group separately
        for( List<String> groupsWords : wordsByLength.values( ) )
        {
            String [ ] words = new String[ groupsWords.size( ) ];
        
            groupsWords.toArray( words );    
            for( int i = 0; i < words.length; i++ )
                for( int j = i + 1; j < words.length; j++ )
                    if( oneCharOff( words[ i ], words[ j ] ) )
                    {
                        update( adjWords, words[ i ], words[ j ] );
                        update( adjWords, words[ j ], words[ i ] );
                    }
        }
        
        return adjWords;
    }
    
    
    // Computes a map in which the keys are words and values are Lists of words
    // that differ in only one character from the corresponding key.
    // Uses an efficient algorithm that is O(N log N) with a TreeMap, or
    // O(N) if a HashMap is used.
    public static Map<String,List<String>> computeAdjacentWords( List<String> words )
    {
        Map<String,List<String>> adjWords = new HashMap<String,List<String>>( );
        Map<Integer,List<String>> wordsByLength = new HashMap<Integer,List<String>>( );
    
          // Group the words by their length
        for( String w : words )
            update( wordsByLength, w.length( ), w );

          // Work on each group separately
        for( Map.Entry<Integer,List<String>> entry : wordsByLength.entrySet( ) )
        {    
            List<String> groupsWords = entry.getValue( );
            int groupNum = entry.getKey( );
            
            // Work on each position in each group
            for( int i = 0; i < groupNum; i++ )
            {
                // Remove one character in specified position, computing representative.
                // Words with same representative are adjacent, so first popular
                // a map
                Map<String,List<String>> repToWord = new HashMap<String,List<String>>( );
                
                for( String str : groupsWords )
                {
                    String rep = str.substring( 0, i ) + str.substring( i + 1 );
                    update( repToWord, rep, str );
                }
                
                // and then look for map values with more than one string
                for( List<String> wordClique : repToWord.values( ) )
                    if( wordClique.size( ) >= 2 )
                        for( String s1 : wordClique )
                            for( String s2 : wordClique )
                                if( s1 != s2 )
                                    update( adjWords, s1, s2 );
            }
        }
        
        return adjWords;
    }
                
    // Find most changeable word: the word that differs in only one
    // character with the most words. Return a list of these words, in case of a tie.
    public static List<String> findMostChangeable( Map<String,List<String>> adjacentWords )
    {
        List<String> mostChangeableWords = new ArrayList<String>( );
        int maxNumberOfAdjacentWords = 0;
        
        for( Map.Entry<String,List<String>> entry : adjacentWords.entrySet( ) )
        {
            List<String> changes = entry.getValue( );
            
            if( changes.size( ) > maxNumberOfAdjacentWords )
            {
                maxNumberOfAdjacentWords = changes.size( );
                mostChangeableWords.clear( );
            }
            if( changes.size( ) == maxNumberOfAdjacentWords )
                mostChangeableWords.add( entry.getKey( ) );
        }
        
        return mostChangeableWords;
    }    
    
    public static void printMostChangeables( List<String> mostChangeable,
                                             Map<String,List<String>> adjacentWords )
    {
        for( String word : mostChangeable )
        {
            System.out.print( word + ":" );
            List<String> adjacents = adjacentWords.get( word );
            for( String str : adjacents )
                System.out.println( " " + str );
            System.out.println( " (" + adjacents.size( ) + " words)" );
        }
    }    
    
    public static void printHighChangeables( Map<String,List<String>> adjacentWords,
                                             int minWords )
    {
        for( Map.Entry<String,List<String>> entry : adjacentWords.entrySet( ) )
        {
            List<String> words = entry.getValue( );
            
            if( words.size( ) >= minWords )
            {
                System.out.print( entry.getKey( ) + " )" + words.size( ) + "):" );
                for( String w : words )
                    System.out.print( " " + w );
                System.out.println( );
            }
        }
    }    
    
    // After the shortest path calculation has run, computes the List that
    // contains the sequence of word changes to get from first to second.
    public static List<String> getChainFromPreviousMap( Map<String,String> prev,
                                                        String first, String second )
    {
        LinkedList<String> result = new LinkedList<String>( );
        
        if( prev.get( second ) != null )
            for( String str = second; str != null; str = prev.get( str ) )
                result.addFirst( str );
        
        return result;
    }
    
    // Runs the shortest path calculation from the adjacency map, returning a List
    // that contains the sequence of words changes to get from first to second.
    public static List<String> findChain( Map<String,List<String>> adjacentWords, String first, String second )            
    {
        Map<String,String> previousWord = new HashMap<String,String>( );
        Queue<String> q = new LinkedList<String>( );
        
        q.add( first );
        while( !q.isEmpty( ) )
        {
            String current = q.element( ); q.remove( );
            List<String> adj = adjacentWords.get( current );
            
            if( adj != null )
                for( String adjWord : adj )
                    if( previousWord.get( adjWord ) == null )
                    {
                        previousWord.put( adjWord, current );
                        q.add( adjWord );
                    }                                                
        }
        
        previousWord.put( first, null );
        
        return getChainFromPreviousMap( previousWord, first, second );
    }
    
    // Runs the shortest path calculation from the original list of words, returning
    // a List that contains the sequence of word changes to get from first to
    // second. Since this calls computeAdjacentWords, it is recommended that the
    // user instead call computeAdjacentWords once and then call other findChar for
    // each word pair.
    public static List<String> findChain( List<String> words, String first, String second )
    {
        Map<String,List<String>> adjacentWords = computeAdjacentWords( words );
        return findChain( adjacentWords, first, second );
    }
    
    public static void main( String [ ] args ) throws IOException
    {
        long start, end;
        
        FileReader fin = new FileReader( "dict.txt" );
        BufferedReader bin = new BufferedReader( fin );
        List<String> words = readWords( bin );
        System.out.println( "Read the words..." + words.size( ) );
        Map<String,List<String>> adjacentWords;
        
        start = System.currentTimeMillis( );
        adjacentWords = computeAdjacentWords( words );
        end = System.currentTimeMillis( );
        System.out.println( "Elapsed time FAST: " + (end-start) );

        start = System.currentTimeMillis( );
        adjacentWords = computeAdjacentWordsMedium( words );
        end = System.currentTimeMillis( );
        System.out.println( "Elapsed time MEDIUM: " + (end-start) );
    
        
        start = System.currentTimeMillis( );
        adjacentWords = computeAdjacentWordsSlow( words );
        end = System.currentTimeMillis( );
        System.out.println( "Elapsed time SLOW: " + (end-start) );

        
        // printHighChangeables( adjacentWords, 15 );
        
        System.out.println( "Adjacents computed..." );
        List<String> mostChangeable = findMostChangeable( adjacentWords );
        System.out.println( "Most changeable computed..." );
        printMostChangeables( mostChangeable, adjacentWords );
        
        BufferedReader in = new BufferedReader( new InputStreamReader( System.in ) );
        
        for( ; ; )
        {
            System.out.println( "Enter two words: " );
            String w1 = in.readLine( );
            String w2 = in.readLine( );
            
            List<String> path = findChain( adjacentWords, w1, w2 );
            System.out.print( path.size( ) + "..." );
            for( String word : path )
                System.out.print( " " + word );
            System.out.println( );    
        }
    }
}
